package algorithm.indexTree;

public class IndexTree2D {

    public static class MyIndexTree2D{

        private int tree[][];
        private int num[][];
        private int R;
        private int C;

        public MyIndexTree2D(int[][] origin){
            this.R = origin.length;
            this.C = origin[0].length;
            tree = new int[R + 1][C + 1];
            num = new int[R][C];
            for (int i = 1; i <= R; i++) {
                for (int j = 1; j <= C; j++) {
                    update(i, j, origin[i - 1][j - 1]);
                }
            }
        }

        public int sum(int row, int col){
            int sum = 0;
            for (int i = row; i > 0; i -= row & (~row + 1)) {
                for (int j = col; j > 0; j -= col & (~col + 1)) {
                    sum += tree[i][j];
                }
            }
            return sum;
        }

        public void update(int row, int col, int value){
            int add = value - num[row - 1][col - 1];
            num[row - 1][col - 1] = value;
            for (int i = row; i <= R; i += row & (~row + 1)) {
                for (int j = col; j <= C; j += col & (~col + 1)) {
                    tree[i][j] += add;
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2){
            return sum(row2, col2) - sum(row2, col1) - sum(row1, col2) + sum(row1, col1);
        }

    }


    public static void main(String[] args) {
        int[][] arr = {{1, 2, 5, 1},{2, 1, 6, 7},{0, 6, 1, 3},{1, 2, 8, 0}};
        MyIndexTree2D myIndexTree2D = new MyIndexTree2D(arr);
        myIndexTree2D.update(3, 3, 3);
        System.out.println(myIndexTree2D.sumRegion(1,1,4,4));
    }

}
